The present invention relates to a technique for constructing a polyhedron model of surfaces of a three-dimensional object from a plurality of sets of digitized data, each set associated with a cross section of the three-dimensional object, and for displaying the surface contour model obtained from the polyhedron model on a graphic display unit; and in particular, to a method for displaying a three-dimentional object which is suitably applicable to fields related to three-dimensional image processing such as the computer aided design (CAD) and computer graphics.
The technique for displaying a surface contour model of an existing three-dimensional object on a graphic display unit are applicable to various practical fields including the medical image processing in which a CT scanner, etc. are used. The display can be considered to mainly comprise three stages, namely:
(i) Technique for constructing the three-dimensional digital image data of an existing object,
(ii) Technique for configuring a polyhedron model of surface contour of the object based on the three-dimensional digital image data, and
(iii) Technique for displaying a clear, comprehensive contour model with smooth surfaces by applying the color interpolation, brightness interpolation, and the like to the polyhedron model resulted from the technique of (ii) above.
These techniques (i) to (iii) can be considered to be associated with an input method, a contour model configuration, and a display method, respectively.
The present invention is primarily related to the technique stage (ii) described above. The following paragraphs describe an operation in which a three-dimensional image data is decomposed into data of points on a plurality of parallel planes, and triangular faces or elements are configured by connecting points on boundaries of images lying on two adjacent planes, which is repeatedly performed for all pairs of adjacent parallel planes, thereby representing the entire shape of the object with the resultant triangular faces or patches. First of all, the method for configuring the contour model will be reviewed in detail. For the format of the three-dimensional digital data of (i), a case in which a series of data N(1), N(2), . . . , N(n) representing data of cross sections of a three-dimensional object, the cross sections corresponding to a plurality of parallel planes passing through the object are given, will be first described herebelow. Each N(i) denotes a two-dimensional image data associated with a cross section on an i-th plane of the object. In the field of present three-dimensional image processing, the obtainable input data is represented in this format in most cases. The procedure of (ii) is ordinarily as follows (FIGS. 1A-1E). In FIG. 1A, a series of crosssection data {N(i)}i=1, 2, . . . , n are first inputted. Next, as shown in FIG. 1B, boundary points are extracted from cross-section data N(i) and N(i+1) on two adjacent planes. In FIG. 1C, based on the series of the boundary points, a polyhedron model is formed with triangular faces which represent or approximate the contour of surfaces of the object between the two adjacent planes. In FIG. 1D, the operations of FIGS. 1(B)-1(C) are repeatedly achieved for all values of i(i=1, . . . , n-1) to construct a polyhedron model of the entire object as shown in FIG. 1E.
Among these processing, the operations related to FIGS. 1B-1C to be executed for the data N(i) and N(i+1) of the two adjacent cross sections are collectively referred to as a fundamental operation herebelow. Automation procedures of this fundamental operation and reduction of human load therefrom have long been desired to be solved.
In the conventional technology, as described in literatures such as "Conversion of Complex Contour Line Definition into Polygonal Element Mosaics", ACM SIGGRAPH'78 Proceedings (1978) by Christiansen and Sederberg and "A New General Triangulation Method for Planar Contours", ACM SIGGRAPH'82 Proceedings (1982) by Ganapathy and Demehy, the processing speed of the fundamental processing has been increased under a restriction that the cross-section data A(i) is enclosed by only one closed broken line (loop) comprisin9 boundary points (for example, as shown in FIGS. 1A-1E). However, the cross-section data N(i) is actually enclosed with a plurality of loops constituted from the boundary points. For example, the N(i) of FIG. 2 are enclosed with two loops .gamma..sub.1 and .gamma..sub.2, while the N(i+1) are enclosed with three loops .GAMMA..sub.1, .GAMMA..sub.2, and .GAMMA..sub.3. To configure the triangular faces in the fundamental operation of FIG. 1C, a loop constituted from the points of N(i) must be related to a loop comprising the points of N(i+1) according to the one-to-one correspondence. Consequently, when the N(i) and N(i+1) each have a loop constituted from a plurality of boundary points, there arises a problem, namely, how to establish the one-to-one correspondence. In the case of FIG. 2, it will be natural to correspond .gamma..sub.1 and .gamma..sub.2 to .GAMMA..sub.1, .GAMMA..sub.2 and .GAMMA..sub.3, respectively. However, even if there exists the correspondence between .gamma..sub.1 and .GAMMA..sub.1 and .GAMMA..sub.2 in this situation, that is, only a one-to-two correspondence is assigned therebetween, so the triangulation cannot be conducted yet (FIG. 3). In other words, a problem to determine pairs between the loops associated with N(i) and those associated with N(i+1) need be solved to create the triangular faces. In this regard, a relatively simple case such as a case associated with the correspondence between .gamma..sub.1 and .GAMMA..sub.1 and .GAMMA.2 of FIG. 3 has already been solved by the prior art technique. The method described in the report by Christiansen is as follows. For simplicity, the description will be made on the assumption that there exists the one-to-two correspondence between the pairs of associated loops.
From the points of loops .GAMMA..sub.1 and .GAMMA..sub.2 as shown in a frame 41 of FIG. 4A, two points t.sub.5 and s.sub.4 having the smallest distance therebetween are selected and an intermediate point m is assigned on a line between the points t.sub.5 and s.sub.4 with the height of the point m with respect to the z coordinate axis set to half the height of t.sub.5 and s.sub.4 (as shown in a frame 42). Thereafter the related nodes are renumbered so as to form a loop (as shown in a frame 43).
Finally, the procedure used when the one-to-one corespondence exists between the loops to be connected to each other is applied to this case, thereby producing the triangular faces (Frame 43).
This procedure, however, as already noted in the Christiansen's report by the author, leads to a meaningless triangulation if it is applied to a case in which the loops on the same plane are quite near to each other and have complex shapes as shown in FIG. 4B(44), where two loops .GAMMA..sub.1 and .GAMMA..sub.2 form the boundary of the cross section on the upper plane and a loop .GAMMA. is the boundary on the lower plane. A solution proposed by Christiansen is as follows. As depicted in a frame 45 of FIG. 4B, points A and E of .GAMMA..sub.1 are connected to B and D of .GAMMA..sub.2, respectively. That is, two loops constituted from the data on the upper plane are substituted by a loop .GAMMA.* including the points A-F, which is corresponded to the loop .gamma. on the lower plane (as shown in a frame 45), thereby generating the triangular faces. This procedure necessitates operator's instruction to be supplied to the computer system.
According to the prior art technology for constructing a polyhedron model as described above, the conversational processing with the computer plays an important role. Consequently, it is desired to develop an efficient method for automatically generating a polyhedron model by use of a computer, thereby minimizing the human load.
The following terms are essential for the description herebelow.
L: Cross section data (denoted as N(i) hereabove) on the lower plane of two adjacent planes. PA1 U: Cross section data (denoted as N(i+1) hereabove) on the upper plane of two adjacent planes. PA1 (i) each extended component is connected and disjoint to each other. And the union of the extended component is equal to the cross section's image on said other plane. PA1 (ii) Every labeled overlapped components on said PA1 (i)' Each extended component is connected and disjoint to each other and the union of the extended component is equal to the cross section's image on said plane. PA1 (ii)' Every labeled overlapped components on said plane is contained in one of the extended components.
A plurality of loops are configured by connecting the boundaries of L and U, where each loop is referred to as a boundary loop herebelow. Among the boundary loops, a loop enclosing an objective domain or component is referred to as an outer boundary, whereas a loop encircling a hole in the objective component is referred to as an inner boundary. Since a component generally has several outer and inner boundaries, each subcomponent enclosed with an outer boundary is referred to as a connected component or simply as a component. For example, if the subcomponents indicated with small solid circles in FIG. 5 constitute an objective component, there exist two connected components, in other words, the number of outer boundaries is two. The connected component in the left-half portion of FIG. 5 includes two inner boundaries. When an outer boundary of a component comprises only one boundary loop, the component is regarded as connected. If a connected component does not include an inner boundary, the connected component is regarded as simply connected.
The method for determining the presence/absence of a hole has already been described in the following literatures, and hence the description thereof will be omitted: Azriel Rosenfeld and Avinash C. Kak; "Digital Picture Processing", Academic Press, Chapters 1 and 9, 1976, "SPIDER User's Manual", Electrotechnical Laboratory Headquarters (image processing package) and "On Topological Property of Sampled Binary Graphics", The Transactions of Institute of Electronics and Communication Engineers of Japan, Section (D), Vol. 56-D, No. 11, pp 662-669 (1973) by Yokoi, Torii, and Fukumura.
According to the fundamental operation, the surface contour of a 3D object between two adjacent planes is represented by a polyhedron model comprising triangular faces. Assume the polyhedron model to be P. It is desired to develop an algorithm for automatically creating the polyhedron P only by inputting the cross section data L and U, thereby significantly reducing the human load required for configuring the polyhedron P.
As already described above, if the cross section data L and U are connected, and specifically, simply connected, the construction of the polyhedron P can be automatically and easily accomplished by use of the prior art procedures. In the general cases, however, as shown in FIGS. 2-3, the boundary loops on the upper plane cannot be related to the boundary loops on the lower plane according to the one-to-one correspondence (in general, the number of the boundary loops varies between the upper and lower planes as depicted in FIGS. 2-3). In addition, if the contours of cross sections are complicated, for example, the contours of the connected components associated with the cross section data on the same plane are considerably near to each other (FIG. 4B) or the cross section data includes holes (FIG. 5), then the conventional method necessarily requires a conversational processing with the computer.
Conditions under which the one-to-one correspondence cannot be established between the boundary loops on the adjacent upper and lower planes will be described. For simplicity, the connected components of the cross section data L and U are assumed to be simply connected. In FIG. 6A, cross sections of a doughnut are indicated by shaded portions. Assuming the cross section data of the first and second planes to be L and U, respectively, this diagram indicates that the number of the connected components is changed from one (=A.sub.1 =L) to two (=B.sub.1 and B.sub.2, B.sub.1 .orgate.B.sub.2 =U), namely, branching takes place. Next, assuming the cross section data of the second and third planes to be L and U, respectively, it is understood that the connected components B.sub.1 and B.sub.2 of L are combined with the connected component C.sub.1 (=U), namely, confluence occurs. If such a branching or confluence appears among the connected components, the one-to-one correspondence cannot be established between the boundary loops on the adjacent upper and lower planes. Moreover, as shown in FIG. 6B, a branching and a confluence may occur among the connected components at the same time, which further complicates the problem to be solved. As described above, when the components of L and U are simply connected, only the outer boundary of each component need be considered; however, if the L and U include holes, the correspondence of inner boundaries must be also taken into consideration.
In any cases, the essential problem is as follows, namely, when the one-to-one correspondence cannot be established between the boundary loops on the two adjacent planes, how the polyhedron P should be configured in the most rational manner? According to the prior art technique as described in connection with the Christiansen's method (FIG. 4A), the automatic processing can be achieved by use of a computer system only when the object has a very simple shape.